In a cloud computing environment, a tenant can reserve one or more virtual machines (VMs), for example, to execute applications. For such applications executed on VMs, the tenant can use information, such as, central processing unit (CPU) usage, memory allocation, etc., to determine application performance. Tenants can also use information related to bandwidth guarantees to determine lower bounds on application performance. However, since cloud networks are shared by multiple tenants in a best efforts manner, cloud providers cannot accurately offer guarantees on the bandwidth that each VM can achieve. The lack of such bandwidth guarantee information prevents tenants from determining lower bounds on application performance. The lack of such bandwidth guarantee information also prevents transfer of enterprise applications to public clouds, since many enterprise applications need predictable performance guarantees.